#!/usr/bin/env python3

"""
Given an input string(s) and pattern(p), implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

Note:
- s could be empty and contain only lowercase letters a-z.
- p could be empty and contain only lowercase letters a-z, and characters like . or *
"""

class Solution:
    
    def is_match(self, text: str, pattern: str) -> bool:
        if not pattern:
            return not bool(text)

        first_match = bool(text) and pattern[0] in { text[0], '.'  }
        if len(pattern) >= 2 and pattern[1] == '*':
            return (self.is_match(text, pattern[2:]) or first_match and self.is_match(text[1:], pattern))
        else:
            return first_match and self.is_match(text[1:], pattern[1:])
            
        
if __name__ == '__main__':
    solution = Solution()
    assert solution.is_match("mississippi", "mis*is*ip*.")
    assert solution.is_match('bbbba', '.*a*a')
    assert solution.is_match("aa", "a*")
    assert not solution.is_match("ab", ".*c")
    assert not solution.is_match("aaa", "aaaa")    
    assert not solution.is_match('aaa', 'ab*a')
    assert solution.is_match('aaa', 'ab*a*c*a')
    assert solution.is_match('aaa', 'a*a')
    assert solution.is_match("aa", "a.")
    assert not solution.is_match("aa", "a")
    assert solution.is_match("ab", ".*")
    assert solution.is_match("aab", "c*a*b")
